package com.shm.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 630. 课程表 III
 * 这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
 *
 * 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
 *
 * 返回你最多可以修读的课程数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
 * 输出：3
 * 解释：
 * 这里一共有 4 门课程，但是你最多可以修 3 门：
 * 首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
 * 第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
 * 第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
 * 第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
 * 示例 2：
 *
 * 输入：courses = [[1,2]]
 * 输出：1
 * 示例 3：
 *
 * 输入：courses = [[3,2],[4,3]]
 * 输出：0
 *
 *
 * 提示:
 *
 * 1 <= courses.length <= 104
 * 1 <= durationi, lastDayi <= 104
 * @author SHM
 */
public class ScheduleCourse {
    /**
     * 方法一：优先队列 + 贪心
     * 思路
     *
     * 对于两门课 (t_1, d_1)(t
     * 1
     * ​
     *  ,d
     * 1
     * ​
     *  ) 和 (t_2, d_2)(t
     * 2
     * ​
     *  ,d
     * 2
     * ​
     *  )，如果后者的关闭时间较晚，即 d_1 \leq d_2d
     * 1
     * ​
     *  ≤d
     * 2
     * ​
     *  ，那么我们先学习前者，再学习后者，总是最优的。这是因为：
     *
     * 设开始学习的时间点为 xx。如果先学习前者，再学习后者，那么需要满足：
     *
     * \begin{cases} x + t_1 \leq d_1 \\ x + t_1 + t_2 \leq d_2 \end{cases}
     * {
     * x+t
     * 1
     * ​
     *  ≤d
     * 1
     * ​
     *
     * x+t
     * 1
     * ​
     *  +t
     * 2
     * ​
     *  ≤d
     * 2
     * ​
     *
     * ​
     *
     *
     * 如果先学习后者，再学习前者，那么需要满足：
     *
     * \begin{cases} x + t_2 \leq d_2 \\ x + t_2 + t_1 \leq d_1 \end{cases}
     * {
     * x+t
     * 2
     * ​
     *  ≤d
     * 2
     * ​
     *
     * x+t
     * 2
     * ​
     *  +t
     * 1
     * ​
     *  ≤d
     * 1
     * ​
     *
     * ​
     *
     *
     * 如果 x + t_2 + t_1 \leq d_1x+t
     * 2
     * ​
     *  +t
     * 1
     * ​
     *  ≤d
     * 1
     * ​
     *   成立，由于 d_1 \leq d_2d
     * 1
     * ​
     *  ≤d
     * 2
     * ​
     *  ，那么 x + t_1 \leq d_1x+t
     * 1
     * ​
     *  ≤d
     * 1
     * ​
     *   和 x + t_1 + t_2 \leq d_2x+t
     * 1
     * ​
     *  +t
     * 2
     * ​
     *  ≤d
     * 2
     * ​
     *   同时成立。这说明如果能「先学习后者，再学习前者」那么一定能「先学习前者，再学习后者」。反之如果 x + t_1 + t_2 \leq d_2x+t
     * 1
     * ​
     *  +t
     * 2
     * ​
     *  ≤d
     * 2
     * ​
     *   成立，则不能推出 x + t_2 + t_1 \leq d_1x+t
     * 2
     * ​
     *  +t
     * 1
     * ​
     *  ≤d
     * 1
     * ​
     *   成立，例如当 x = 0x=0, (t_1, d_1) = (2, 3)(t
     * 1
     * ​
     *  ,d
     * 1
     * ​
     *  )=(2,3)，(t_2, d_2) = (5, 100)(t
     * 2
     * ​
     *  ,d
     * 2
     * ​
     *  )=(5,100) 时，虽然能「先学习前者，再学习后者」，但不能「先学习后者，再学习前者」。
     *
     * 因此，我们可以讲所有的课程按照关闭时间 dd 进行升序排序，再依次挑选课程并按照顺序进行学习。
     *
     * 在遍历的过程中，假设我们当前遍历到了第 ii 门课 (t_i, d_i)(t
     * i
     * ​
     *  ,d
     * i
     * ​
     *  )，而在前 i-1i−1 门课程中我们选择了 kk 门课 (t_{x_1}, d_{x_1}), (t_{x_2}, d_{x_2}), \cdots, (t_{x_k}, d_{x_k})(t
     * x
     * 1
     * ​
     *
     * ​
     *  ,d
     * x
     * 1
     * ​
     *
     * ​
     *  ),(t
     * x
     * 2
     * ​
     *
     * ​
     *  ,d
     * x
     * 2
     * ​
     *
     * ​
     *  ),⋯,(t
     * x
     * k
     * ​
     *
     * ​
     *  ,d
     * x
     * k
     * ​
     *
     * ​
     *  )，满足 x_1 < x_2 < \cdots < x_kx
     * 1
     * ​
     *  <x
     * 2
     * ​
     *  <⋯<x
     * k
     * ​
     *  ，那么有：
     *
     * \begin{cases} t_{x_1} \leq d_{x_1} \\ t_{x_1} + t_{x_2} \leq d_{x_2} \\ \cdots \\ t_{x_1} + t_{x_2} + \cdots + t_{x_k} \leq d_{x_k} \end{cases}
     * ⎩
     * ⎪
     * ⎪
     * ⎪
     * ⎪
     * ⎨
     * ⎪
     * ⎪
     * ⎪
     * ⎪
     * ⎧
     * ​
     *
     * t
     * x
     * 1
     * ​
     *
     * ​
     *  ≤d
     * x
     * 1
     * ​
     *
     * ​
     *
     * t
     * x
     * 1
     * ​
     *
     * ​
     *  +t
     * x
     * 2
     * ​
     *
     * ​
     *  ≤d
     * x
     * 2
     * ​
     *
     * ​
     *
     * ⋯
     * t
     * x
     * 1
     * ​
     *
     * ​
     *  +t
     * x
     * 2
     * ​
     *
     * ​
     *  +⋯+t
     * x
     * k
     * ​
     *
     * ​
     *  ≤d
     * x
     * k
     * ​
     *
     * ​
     *
     * ​
     *
     *
     * 如果上述选择方案是前 i-1i−1 门课程的「最优方案」：即不存在能选择 k+1k+1 门课程的方法，也不存在能选择 kk 门课程，并且总时长更短（小于 t_{x_1} + t_{x_2} + \cdots + t_{x_k}t
     * x
     * 1
     * ​
     *
     * ​
     *  +t
     * x
     * 2
     * ​
     *
     * ​
     *  +⋯+t
     * x
     * k
     * ​
     *
     * ​
     *  ）的方案，那么我们可以基于该方案与第 ii 门课程 (t_i, d_i)(t
     * i
     * ​
     *  ,d
     * i
     * ​
     *  )，构造出前 ii 门课程的最优方案：
     *
     * 如果 t_{x_1} + t_{x_2} + \cdots + t_{x_k} + t_i \leq d_it
     * x
     * 1
     * ​
     *
     * ​
     *  +t
     * x
     * 2
     * ​
     *
     * ​
     *  +⋯+t
     * x
     * k
     * ​
     *
     * ​
     *  +t
     * i
     * ​
     *  ≤d
     * i
     * ​
     *  ，那么我们可以将第 ii 门课程 (t_i, d_i)(t
     * i
     * ​
     *  ,d
     * i
     * ​
     *  ) 直接加入方案，得到选择 k+1k+1 门课程的最优方案。
     *
     * 这里的「最优性」可以使用反证法来证明。如果存在更优的方案，那么该方案一定包含 (t_i, d_i)(t
     * i
     * ​
     *  ,d
     * i
     * ​
     *  )，如果不包含，那么说明前 i-1i−1 门课程就存在更优的方案，这与我们的假设相矛盾。当最优方案包含 (t_i, d_i)(t
     * i
     * ​
     *  ,d
     * i
     * ​
     *  ) 时，根据之前的证明，「先学习前者，再学习后者」总是最优的，我们就可以把 (t_i, d_i)(t
     * i
     * ​
     *  ,d
     * i
     * ​
     *  ) 作为该方案的最后一门课程。由于该方案优于选择 x_1, x_2, \cdots, x_k, ix
     * 1
     * ​
     *  ,x
     * 2
     * ​
     *  ,⋯,x
     * k
     * ​
     *  ,i 的构造方案，因此同时将最后一门课程 ii 去除后，该方案仍然优于选择 x_1, x_2, \cdots, x_kx
     * 1
     * ​
     *  ,x
     * 2
     * ​
     *  ,⋯,x
     * k
     * ​
     *   的方案，同样说明前 i-1i−1 门课程存在更优的方案，这与我们的假设相矛盾。
     *
     * 如果 t_{x_1} + t_{x_2} + \cdots + t_{x_k} + t_i > d_it
     * x
     * 1
     * ​
     *
     * ​
     *  +t
     * x
     * 2
     * ​
     *
     * ​
     *  +⋯+t
     * x
     * k
     * ​
     *
     * ​
     *  +t
     * i
     * ​
     *  >d
     * i
     * ​
     *  ，那么我们无法将第 ii 门课程 (t_i, d_i)(t
     * i
     * ​
     *  ,d
     * i
     * ​
     *  ) 直接加入方案。我们可以使用类似的反证法，证明出此时前 ii 门课程不可能存在选择 k+1k+1 门课程的更优方案，因此我们的目标仍然为选择 kk 门课程，但最小化它们的总时间，为后续的课程腾出更多的时间。
     *
     * 如果 t_{x_1}, t_{x_2}, \cdots, t_{x_k}t
     * x
     * 1
     * ​
     *
     * ​
     *  ,t
     * x
     * 2
     * ​
     *
     * ​
     *  ,⋯,t
     * x
     * k
     * ​
     *
     * ​
     *   都小于等于 t_it
     * i
     * ​
     *  ，那么我们显然没有办法通过第 ii 门课来使得总时间更小。但如果其中时间最长的那门课（记为 t_{x_j}t
     * x
     * j
     * ​
     *
     * ​
     *  ）满足 t_{x_j} > t_it
     * x
     * j
     * ​
     *
     * ​
     *  >t
     * i
     * ​
     *  ，那么我们就可以尝试将第 x_jx
     * j
     * ​
     *   门课程替换成第 ii 门课程了。这样的替换会使得总时间减少 t_{x_j} - t_it
     * x
     * j
     * ​
     *
     * ​
     *  −t
     * i
     * ​
     *  ，也是我们能做到的减少的上限了。
     *
     * 那么将第 x_jx
     * j
     * ​
     *   门课程替换成第 ii 门课程后，这些课程是否满足题目的要求呢？我们将这些课程按照 x_1, x_2, \cdots, x_{j-1}, x_{j+1}, \cdots, x_k, ix
     * 1
     * ​
     *  ,x
     * 2
     * ​
     *  ,⋯,x
     * j−1
     * ​
     *  ,x
     * j+1
     * ​
     *  ,⋯,x
     * k
     * ​
     *  ,i 的顺序进行学习：
     *
     * 对于 x_1, x_2, \cdots, x_{j-1}x
     * 1
     * ​
     *  ,x
     * 2
     * ​
     *  ,⋯,x
     * j−1
     * ​
     *  ，它们需要满足的不等式与之前是一致的，因此仍然满足要求；
     *
     * 对于 x_{j+1}, \cdots, x_{k}x
     * j+1
     * ​
     *  ,⋯,x
     * k
     * ​
     *  ，原先需要满足的不等式的左侧少了 t_{x_j}t
     * x
     * j
     * ​
     *
     * ​
     *   这一项，由于是左侧 \leq≤ 右侧，因此仍然满足要求；
     *
     * 对于 ii，由于 t_{x_1} + t_{x_2} + \cdots + t_{x_k} \leq d_{x_k}t
     * x
     * 1
     * ​
     *
     * ​
     *  +t
     * x
     * 2
     * ​
     *
     * ​
     *  +⋯+t
     * x
     * k
     * ​
     *
     * ​
     *  ≤d
     * x
     * k
     * ​
     *
     * ​
     *   成立，而 t_{x_{j}} > t_it
     * x
     * j
     * ​
     *
     * ​
     *  >t
     * i
     * ​
     *  ，因此：
     *
     * t_{x_1} + t_{x_2} + \cdots + t_{x_{j-1}} + t_{x_{j+1}} + \cdots + t_{x_k} + t_i \leq d_{x_k}
     * t
     * x
     * 1
     * ​
     *
     * ​
     *  +t
     * x
     * 2
     * ​
     *
     * ​
     *  +⋯+t
     * x
     * j−1
     * ​
     *
     * ​
     *  +t
     * x
     * j+1
     * ​
     *
     * ​
     *  +⋯+t
     * x
     * k
     * ​
     *
     * ​
     *  +t
     * i
     * ​
     *  ≤d
     * x
     * k
     * ​
     *
     * ​
     *
     *
     * 满足要求。
     *
     * 这就说明我们可以将第 x_jx
     * j
     * ​
     *   门课程替换成第 ii 门课程。
     *
     * 这样一来，当我们遍历完所有的 nn 门课程后，就可以得到最终的答案。
     *
     * 算法
     *
     * 我们需要一个数据结构支持「取出 tt 值最大的那门课程」，因此我们可以使用优先队列（大根堆）。
     *
     * 我们依次遍历每一门课程，当遍历到 (t_i, d_i)(t
     * i
     * ​
     *  ,d
     * i
     * ​
     *  ) 时：
     *
     * 如果当前优先队列中所有课程的总时间与 t_it
     * i
     * ​
     *   之和小于等于 d_id
     * i
     * ​
     *  ，那么我们就把 t_it
     * i
     * ​
     *   加入优先队列中；
     *
     * 如果当前优先队列中所有课程的总时间与 t_it
     * i
     * ​
     *   之和大于 d_id
     * i
     * ​
     *  ，那么我们找到优先队列中的最大元素 t_{x_j}t
     * x
     * j
     * ​
     *
     * ​
     *  。如果 t_{x_j} > t_it
     * x
     * j
     * ​
     *
     * ​
     *  >t
     * i
     * ​
     *  ，则将它移出优先队列，并把 t_it
     * i
     * ​
     *   加入优先队列中。
     *
     * 在遍历完成后，优先队列中包含的元素个数即为答案。
     * 复杂度分析
     *
     * 时间复杂度：O(n \log n)O(nlogn)。排序需要 O(n \log n)O(nlogn) 的时间，优先队列的单次操作需要 O(\log n)O(logn) 的时间，每个任务会最多被放入和取出优先队列一次，这一部分的时间复杂度为 O(n \log n)O(nlogn)。因此总时间复杂度也为 O(n \log n)O(nlogn)。
     *
     * 空间复杂度：O(n)O(n)，即为优先队列需要使用的空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/course-schedule-iii/solution/ke-cheng-biao-iii-by-leetcode-solution-yoyz/
     * @param courses
     * @return
     */
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses,(a,b)->a[1]-b[1]);
        PriorityQueue<Integer>  q=new PriorityQueue<>((a,b)->b-a);
        int total = 0;
        for (int[] course : courses) {
            int ti = course[0],di=course[1];
            if (total+ti<=di){
                total+=ti;
                q.offer(ti);
            }else if (!q.isEmpty()&&q.peek()>ti){
                total-=q.poll();
                total+=ti;
                q.offer(ti);
            }
        }
        return q.size();
    }
}
